package com.company.Sort;

import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}11:21
 */
public class RadixSort {//基数排序
    public static void main(String[] args) {
        int arr[] = {53,3,542,748,14,214};
        radixSort(arr);
    }

    public static void radixSort(int[] arr) {
        //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
        //说明：二维数组包含10个二维数组、数据溢出，则每个一维数组（桶）,大小定位arr.length
        //基数排序是明显的空间换时间
        int[][] bucket = new int[10][arr.length];

        //为了记录每个桶中，实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //可以这里理解
        //比如：bucketElementCounts[0],记录的就是 bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];  //该数组中对应的值是对应bucket二维数组中的行数组

        //找到数组中最大的数，并且算出位数
        int max = 0;
        for (int s:arr){
            if (s>max){
                max = s;
            }
        }
        int maxlength = (max+"").length();
        //第一轮 个位数
        for (int i = 0; i < maxlength;i++) {
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的个数
                if (i == 0) {
                    int digitOfElement = arr[j] % 10;
                    bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                    bucketElementCounts[digitOfElement]++;
                }else {
                    int digitOfElement = arr[j] /(int) Math.pow(10,i) % 10;
                    bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                    bucketElementCounts[digitOfElement]++;
                }
            }

            int index = 0;
            //遍历每一个桶，并将桶中的数据，放入到原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中有数据才放入到原数组
                if (bucketElementCounts[k] != 0) {
                    //循环该桶，放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入到arr中
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                bucketElementCounts[k] = 0;
            }
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void radixSort2(int[] arr) {
        //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
        //说明：二维数组包含10个二维数组、数据溢出，则每个一维数组（桶）,大小定位arr.length
        //基数排序是明显的空间换时间
        int[][] bucket = new int[10][arr.length];

        //为了记录每个桶中，实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //可以这里理解
        //比如：bucketElementCounts[0],记录的就是 bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];  //该数组中对应的值是对应bucket二维数组中的行数组

        //第一轮 个位数
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个数
            int digitOfElement = arr[j] /10 % 10;
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        int index = 0;
        //遍历每一个桶，并将桶中的数据，放入到原数组
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶中有数据才放入到原数组
            if (bucketElementCounts[k] != 0){
                //循环该桶，放入
                for (int l = 0; l < bucketElementCounts[k];l++){
                    //取出元素放入到arr中
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort3(int[] arr) {
        //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
        //说明：二维数组包含10个二维数组、数据溢出，则每个一维数组（桶）,大小定位arr.length
        //基数排序是明显的空间换时间
        int[][] bucket = new int[10][arr.length];

        //为了记录每个桶中，实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //可以这里理解
        //比如：bucketElementCounts[0],记录的就是 bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];  //该数组中对应的值是对应bucket二维数组中的行数组

        //第一轮 个位数
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个数
            int digitOfElement = arr[j] /100 % 10;
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        int index = 0;
        //遍历每一个桶，并将桶中的数据，放入到原数组
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶中有数据才放入到原数组
            if (bucketElementCounts[k] != 0){
                //循环该桶，放入
                for (int l = 0; l < bucketElementCounts[k];l++){
                    //取出元素放入到arr中
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
